home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / pers_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.7 KB  |  235 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  pers_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PERS_TREE_H
  17. #define LEDA_PERS_TREE_H
  18.  
  19. #include <LEDA/basic.h>
  20. #include <LEDA/list.h>
  21.  
  22. typedef void (*DRAW_NODE_FCT)(double,double,void*);
  23. typedef void (*DRAW_EDGE_FCT)(double,double,double,double);
  24.  
  25. /* implementation of a node of the ephemeral red-black tree of a specific
  26.  * persistent  node, where the colors of that persistent node through the
  27.  * various versions can be found
  28.  */
  29.  
  30. class pers_tree_node;
  31. class C_pers_tree_node;
  32. class F_pers_tree_node;
  33. class VER_pers_tree_node;
  34.  
  35. typedef list_item Version;
  36.  
  37.  
  38. class C_pers_tree_node
  39. {
  40.   friend class pers_rb_tree;
  41.  
  42.   Version vers_stamp;
  43.   C_pers_tree_node* c_link[3];
  44.   int c_right;
  45.   int c_color;
  46.   int col_value;
  47.  
  48.   LEDA_MEMORY(C_pers_tree_node)
  49. };
  50.  
  51. /* implementation of a node of the  ephemeral red-black tree of a specific
  52.  * persistent node, where the children of that persistent node through the
  53.  * various versions can be found
  54.  */
  55.  
  56. class F_pers_tree_node
  57. {
  58.   friend class pers_rb_tree;
  59.  
  60.   Version ver_stamp;
  61.   F_pers_tree_node* f_link[3];
  62.   int f_right;
  63.   int f_color;
  64.   pers_tree_node* poin_value;
  65.  
  66.   LEDA_MEMORY(F_pers_tree_node)
  67. };
  68.  
  69.  
  70. /* implementation of a persistent node */
  71.  
  72. class pers_tree_node
  73. {
  74.   friend class pers_rb_tree;
  75.  
  76.   void *key;
  77.   void *info;
  78.   pers_tree_node *parent;
  79.   int right;
  80.   int is_leaf;
  81.   F_pers_tree_node *link[2];
  82.   C_pers_tree_node *red;
  83.   F_pers_tree_node *copy;
  84.  
  85.   pers_tree_node* next;  // linking all used pers_tree_nodeS
  86.  
  87.   LEDA_MEMORY(pers_tree_node)
  88. };
  89.  
  90. /* implementation of a node (or member) of the version list */
  91.  
  92. class VER_pers_tree_node
  93. { 
  94.   friend class pers_rb_tree;
  95.  
  96.   pers_tree_node*  acc_pointer;
  97.   int    popul;
  98.   double ser_num;
  99.  
  100.   LEDA_MEMORY(VER_pers_tree_node)
  101. };
  102.  
  103. typedef VER_pers_tree_node* ver_node;
  104.  
  105.  
  106.  
  107. struct V_LIST {
  108.  
  109. list<ver_node> vl;
  110. int count;
  111. pers_tree_node* used;
  112.  
  113. };
  114.  
  115.  
  116.  
  117. class pers_rb_tree {
  118.  
  119. protected:
  120.  
  121. V_LIST* v_list;
  122.  
  123. virtual int cmp_keys(GenPtr x, GenPtr y) { return compare(x,y); }
  124. virtual void print_key(GenPtr x) { Print(x); }
  125. virtual void copy_key(GenPtr&)   {}
  126. virtual void copy_inf(GenPtr&)   {}
  127. virtual void clear_key(GenPtr&)  {}
  128. virtual void clear_inf(GenPtr&)  {}
  129.  
  130.  
  131. pers_tree_node* child(int leftright, pers_tree_node *p, Version i)
  132. { return(acc_step(p->link[leftright], i)); }
  133.  
  134. void* get_key(pers_tree_node *p, Version i)
  135. { return (acc_step(p->copy, i))->key; }
  136.  
  137. int isleaf(pers_tree_node *p) 
  138. { //return (p == p->link[0]->poin_value); 
  139.   return p->is_leaf;
  140.  }
  141.   
  142. pers_tree_node* sibling(pers_tree_node *p, Version i)
  143. { return acc_step(p->parent->link[1 - p->right], i); } 
  144.  
  145.  
  146. /* define the order of versions in the version list */
  147. int vless(Version x, Version y)    
  148. { return  (v_list->vl[x]->ser_num < v_list->vl[y]->ser_num); }
  149.  
  150. /* find the next to a given version in the version list */ 
  151. Version  iplus(Version i)
  152. { return v_list->vl.succ(i); }
  153.  
  154.  
  155. pers_tree_node*   acc_step(F_pers_tree_node *, Version);
  156. Version new_version(Version);
  157. void    m_b_root(Version);
  158.  
  159. F_pers_tree_node* f_nleaf(pers_tree_node*, Version);
  160. F_pers_tree_node* f_nnode(F_pers_tree_node*, F_pers_tree_node*);
  161. F_pers_tree_node* f_rbsearch(F_pers_tree_node* p, Version);
  162. void    f_rbclear(F_pers_tree_node*);
  163. int     f_insert(F_pers_tree_node*, pers_tree_node*, Version);
  164. void    f_single_rot(F_pers_tree_node*, int);
  165. void    f_double_rot(F_pers_tree_node*, int);
  166.  
  167. C_pers_tree_node* c_nleaf(int, Version);
  168. C_pers_tree_node* c_nnode(C_pers_tree_node*, C_pers_tree_node*);
  169. C_pers_tree_node* c_rbsearch(C_pers_tree_node* p, Version);
  170. void    c_rbclear(C_pers_tree_node*);
  171. int     c_insert(C_pers_tree_node*, int, Version);
  172. void    c_single_rot(C_pers_tree_node*, int);
  173. void    c_double_rot(C_pers_tree_node*, int);
  174.  
  175. pers_tree_node*   single_rot(pers_tree_node* top_node, int dir, Version i);
  176. pers_tree_node*   double_rot(pers_tree_node* top_node, int dir, Version i);
  177. pers_tree_node*   newnode(pers_tree_node* c1, pers_tree_node* c2, Version i);
  178. pers_tree_node*   newleaf(void* val, void* inf, pers_tree_node*, pers_tree_node*, Version i);
  179. int     isred(pers_tree_node* p, Version i);
  180. void    up_col(C_pers_tree_node* p, int newvalue, Version i);
  181. void    update(F_pers_tree_node* p, pers_tree_node* newvalue, Version i);
  182.  
  183. pers_tree_node*   search(void* val, Version i)     { pers_tree_node* p; return search(val,p,i);}
  184. pers_tree_node*   search(void*, pers_tree_node*&, Version);
  185.  
  186.  
  187. public:
  188.  
  189.  pers_rb_tree() {}
  190. virtual ~pers_rb_tree() {}
  191.  
  192. void init_tree();
  193.  
  194. void* key(pers_tree_node* p)  { return p->key; }
  195. void* inf(pers_tree_node* p)  { return p->info; }
  196.  
  197. Version copy_version(Version);
  198. void    del_version(Version);
  199.  
  200. Version del(void*, Version);
  201. Version insert(void*, void*, Version);
  202. Version change_inf(pers_tree_node*,void*,Version);
  203.  
  204. pers_tree_node* lookup(void *val,Version v);
  205. pers_tree_node* locate(void *val,Version v);
  206. pers_tree_node* locate_pred(void *val,Version v);
  207. pers_tree_node* min(Version v);
  208. pers_tree_node* max(Version v);
  209. pers_tree_node* succ(pers_tree_node* p, Version v) { return child(1,p,v); }
  210. pers_tree_node* pred(pers_tree_node* p, Version v) { return child(0,p,v); }
  211.  
  212. int   size(Version v) { return v_list->vl[v]->popul; }
  213.  
  214. double ver_num(Version v)  { return v_list->vl[v]->ser_num; }
  215.  
  216. void print(pers_tree_node*,Version);
  217.  
  218. void del_tree();
  219.  
  220. void print(Version v) 
  221. { //cout << form("%5f : ",v_list->vl[v]->ser_num);
  222.   print(v_list->vl[v]->acc_pointer,v);
  223.   newline;
  224.  }
  225.  
  226. void draw(DRAW_NODE_FCT,DRAW_EDGE_FCT, Version, pers_tree_node*, double, double, double, double, double);
  227.  
  228. void draw(DRAW_NODE_FCT,DRAW_EDGE_FCT, Version, double, double, double, double);
  229.  
  230. };
  231.  
  232.  
  233. #endif
  234.  
  235.